1. Field of the Invention
The present invention relates to image processing by interpolation so as to obtain interpolated values between pixels in an existing image. In particular, the invention pertains to interpolation based on the existence of diagonal gradients in image data.
2. Description of the Related Art
Scaling is one common form of image processing, whereby image data of a first size is scaled to image data of a second size. Consider, for example, a situation in which a computer user is viewing image data on a computer screen, which physically appears to the user as having measurements of 31/2.times.5 inches. Given screen resolution of 72 dpi (dots per inch), the image data measures 252.times.360 pixels. If such an image were thereafter to be printed, given a printer resolution of 600 dpi, the image would be printed to a size of 0.42.times.0.60 inches, which would be entirely unacceptable to the user. Accordingly, before printing, the image data originally comprised by 252.times.360 pixels must be scaled to a size of 2100.times.3000 pixels, so that when printed on the 600 dpi printer the resulting image again measures 31/2.times.5 inches.
To scale images from a first pixel dimension to a second pixel dimension, interpolation is generally unavoidable. Interpolation is a procedure by which image data for pixels between existing pixels of the source image is derived. Many interpolation techniques have been proposed, such as bi-linear, bi-cubic and two-step linear interpolation. These techniques usually use the four (or more) surrounding pixels of existing data in order to derive pixel data for a target pixel.
Two-step linear interpolation will now be explained with reference to FIG. 4. As shown in FIG. 4, destination image data of size Q pixels high by R pixels wide is desired to be derived from source image data of size M pixels high by N pixels wide. With two-step linear interpolation, to derive a data value for a pixel in the destination image, data values for the four corresponding nearest neighbor pixels in the source image are found, and these four data values are interpolated horizontally to form two intermediate horizontal data values. These two intermediate data values are then further interpolated vertically to form the data value for the desired pixel in the destination image.
Specifically, and again referring to FIG. 4, to derive a data value for the pixel at position (r, q) in the destination image, the corresponding position (n, m) in the source image is derived using simple scaling equations as follows: ##EQU1##
Data values V.sub.1, V.sub.2, V.sub.3 and V.sub.4 for the four corresponding nearest neighbor pixels in the source image are then found. Values for these four pixels are interpolated horizontally and then vertically, using the following interpolation equation so as to obtain a value V for the target pixel at (r, q) in the destination image: EQU V=(V.sub.1 (1-x)+V.sub.2 x)(1-y)+(V.sub.3 (1-x)+V.sub.4 x)y
where x is the horizontal distance in the source image between the location of the target pixel and the location of the nearest neighbor pixel to the left of the target pixel, and where y is the vertical distance in the source image between the location of the target pixel and the location of the nearest neighbor pixel above the target pixel.
Mathematically, it can be shown that the foregoing equation is the same as the following equation, which can be interpreted based on relative areas: EQU V=V.sub.1 (1-x)(1-y)+V.sub.2 (x)(1-y)+V.sub.3 (1-x)(y)+V.sub.4 (x)(y)
Although such interpolation methods produce acceptable results in many situations, one situation in which these interpolation methods fail is where diagonal gradients or lines are present in the source image. When scaled, diagonal gradients and lines produce distortions that manifest themselves as periodic zigzag structures (also known as staircasing), corresponding to an aliasing that is introduced by the interpolation.
An example of these distortions is illustrated in FIGS. 1a through 1d. FIG. 1a is a view of an image with diagonal gradients scanned at 300 dpi. FIG. 1b is an enlarged view of the same image scanned at 600 dpi. It is desired in this example to scale the image shown in FIG. 1a up to the resolution of the image shown in FIG. 1b. In order to accomplish this scaling, pixel interpolation must be performed. FIG. 1c shows the result of scaling performed by a conventional pixel interpolation method, which has produced aliasing. This aliasing is evident in the staircasing pattern shown in FIG. 1c, which was not in the source image shown in FIG. 1a and which is an unwanted distortion of the image.
While other interpolation techniques such as bi-linear and bi-cubic interpolation tend to minimize such aliasing artifacts, these interpolation methods often decrease performance and sometimes do not reduce aliasing to any significant extent.